package com.qch.edu.Tree;


import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author qch
 * @Date 2021/3/13
 * 按层遍历
 *1） 二叉树宽度遍历，用队列
 * queue.poll()
 * 打印宽度(经典面试题)：发现新一层的开始 Map<key,value> key在那一层 ，currentLevelNodes  进去不算，出来的时候+1
 */
public class FloorTree {

    public static  int maxWidthUseMap(Node head){
        if(head==null){
            return 0;
        }
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(head);
        //key在那一层->value(value指Node在哪一层)
        HashMap<Node,Integer>levelMap=new HashMap<Node, Integer>();
        levelMap.put(head,1);
        int currentLevel=1;//当你正在统计哪一层的高度
        int currentLevelNodes=0;//当前currentLevel层，宽度目前是多少
        int max =0;
        while (!queue.isEmpty()){
            Node cur=queue.poll();
            int currentNodeLevel=levelMap.get(cur);
            if(cur.getLeft()!=null){
                levelMap.put(cur.getLeft(),currentNodeLevel+1);
                queue.add(cur.getLeft());
            }
            if(cur.getRight()!=null){
                levelMap.put(cur.getRight(),currentNodeLevel+1);
                queue.add(cur.getRight());
            }
            if(currentNodeLevel==currentLevel){
                currentLevelNodes++;
            }else {
                max=Math.max(max,currentLevelNodes);
                currentLevel++;
                currentLevelNodes=1;
            }
        }
        //最后一层因为不会触发更新所以需要再结算一次
        max=Math.max(max,currentLevelNodes);
        return max;
    }
    public static  int maxWidthNoMap(Node head){
        if(head==null){
            return 0;
        }
        int currEnd=0;
        int nextEnd=0;
    return 0;}
}
